Current production processes are generally complex and have a large number of production steps which are coupled to one another. As a result, there are one or more final products which were produced via a chain of intermediate products from starting products.
The planning of production processes is typically oriented to a demand for a final product at a specific time, the quantity of starting products to be processed and the time window for the individual production steps resulting therefrom. The demand for the final products is estimated from a prognosis function and the target inventory quantity for the periods observed is determined therefrom, taking a storage reserve into consideration. The prognosis function is typically determined empirically or using a prognosis method. The target inventory quantity, which may change over time, represents an essential starting parameter for the optimization of the production process.
The current methods for production planning essentially follow a formulation in which the capacity planning to be optimized is modeled as a linear planning problem (LP problem), the LP problem being solved using commercial products and being implemented in a production plan using a downstream scheduling strategy, which is often heuristic. Commercial products which are used to solve the LP problem are, for example, standard LP solvers, such as those offered by the companies ILOG or dash optimization.
If only one single product is planned, the capacity plan also automatically provides a production plan. This is frequently no longer relevant for multiple products, since the LP solution only provides capacity utilizations for certain time intervals. For the preparation of an optimum production plan for more than one product, a downstream, combinational problem is therefore to be solved. Since such combinational problems are only solvable with exponential computing outlay because of the mathematical complexity, the combinational solution is therefore excluded for problems relevant in practice from a very small number of products (approximately 5). Therefore, one attempts to avoid the significant computing outlay using task-, location-, and/or product-specific scheduling strategies which are based on heuristic methods.
A balanced quantity plan provides little or no information on whether and how a sequence plan which may be implemented is to appear. The sequence planning is completely decoupled from the capacity planning. Joint optimization of capacity and sequence plans is therefore not possible. Even productions having fixed plans and/or which have already begun may only be taken into consideration in the preparation of the production plan with great difficulty. Therefore, the production plan derived in this way no longer corresponds to the original capacity planning, and the quantity balance sheets which represent a minimum requirement for a production plan are no longer balanced, for example. For “batch productions” and/or “campaign formations”, the material balance sheets must be checked again and again and possibly corrected. This increases the maintenance outlay of the planning significantly. These problems require increased caretaking, sometimes with very complex individual programming.
The modulation of the LP problem is performed in two parts using methods according to the related art. First, for the capacity planning, a supply-network planning model is used in which neither sequence restrictions, lot size restrictions, temporal restrictions, storability restrictions, pass-through times, or other things may be imaged correctly. The more detailed planning is left to a second model in a second step which performs the planning of the production sequences with the aid of heuristic rules, such as a scheduling strategy. These heuristic rules are frequently overtaxed with the capacity and/or storage optimization.
Because the modulation is performed in two steps, it may not be ensured that the goals of the capacity planning and the production sequences are taken into consideration jointly during the construction of the production plan. The practice of production planning shows that significant manual corrections are to be performed by the user. In this case, the unreliable results, whose quality is highly doubtful, represent a large disadvantage. In addition, this method is very susceptible to errors, since production-specific restrictions and finite capacities are to be taken into consideration manually and simultaneously by the planning person and facility capacities may frequently be assigned by multiple persons. A synchronization problem then arises between multiple planning persons if they modify the same resource.
For the reasons cited above, production planning with the aid of a model tailored for an LP solver leads to unacceptable and unfeasible production plans. It is especially disadvantageous that only linear dependencies may be imaged using an LP model (quantity balance sheets such as “the product A must first be produced before it is consumed” correspond to linear equations or capacity restrictions, such as a maximum production rate, correspond to inequalities). A realistic planning situation may be described only insufficiently using linear restrictions, however.
In order to be able to guarantee the preparation of a viable plan, other dependencies are necessary for modeling qualitatively, which may be described only poorly or not at all using linear equations or inequalities. These essential restrictions include                non-linear conditions (“at a specific time, fractions of a product may not be produced on a facility, but rather none or precisely one. A plan quantity must always be a multiple of a batch quantity.”),        sequence-dependent conditions (“For the production steps 1, 2, and 3, the product A may never be produced before the product B.”), or        storability restrictions (“product A may not be stored temporarily for longer than two days.”).        
These and similar restrictions require the introduction of integrity conditions and/or binary variables and lead to an MILP model (MILP=mixed integer LP). This is an expansion of an LP model using integrity conditions.
MILP problems may not be solved using the standard techniques of an LP server and require completely different solution techniques. In order to be able to compute the optimum solution of an MILP problem, in general, all possible assignments of the integrity conditions must be analyzed and compared. Viewed from a mathematical standpoint, this is an NP-complete problem. In practice, this means that it may not be solved like an LP problem, for example, in polynomial computing time as a function of the parameters described, but rather that an exponential computing outlay is necessary for this purpose as a function of the number of integrity conditions.
If it is assumed that an MILP problem having ten integrity conditions for a product may be solved in a specific time, then this same task requires 32 times as much time with 15 products and 1024 times as much time with 20 products. An MILP problem may therefore only be solved in a justifiable time with very few integrity conditions. This restriction, which is purely a matter of computing technology, is the essential reason the non-linear, sequence-dependent restrictions or storability restrictions are either completely ignored or only an insufficiently small number of machines, products, and planning periods are permitted in the MILP model observed.